/*
 * @Author: gitee_com_zb
 * @Date: 2024-12-09 10:17:39
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-12-09 10:17:57
 * @FilePath: /algorithm/每日一题9.最小覆盖子串(hard).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/minimum-window-substring
 */
class Solution {
public:
    // 滑动窗口 + 哈希统计 时间复杂度:O(N)
    string minWindow(string s, string t) {
        int hash1[128] = { 0 }; // 统计t中字符的频率
        int kinds = 0; // 统计t中字符的种类
        for(auto ch : t) {
            if(hash1[ch] == 0) kinds++;
            hash1[ch]++;
        }
        int hash2[128] = { 0 }; // 统计滑动窗口中字符的频率
        int n = s.size();
        int minlen = INT_MAX, begin = -1;
        for(int left = 0, right = 0, count = 0;right <= n; right++) {
            char in = s[right];
            hash2[in]++;
            if(hash2[in] == hash1[in]) count++;  // 进窗口 + 维护count(满足要求的有效字符的种类数)
            while(count == kinds) { // 判断 
                if(right - left + 1 < minlen) { // 更新结果
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out] == hash1[out]) count--; // 出窗口 + 维护count
                hash2[out]--;
            }
        }
        return begin == -1 ? "" : s.substr(begin,minlen);
    }
};